As is known in the art, it is frequently desirable to detect and segment an image of an object from a background of other objects and/or from a background of noise. One application, for example, is in CT or MRI where it is desired to segment an anatomical feature of a human patient, such as, for example, a vertebra of the patient. In other cases it would be desirable to segment a moving, deformable anatomical feature such as the heart.
The amount of information contained in medical images can become overwhelming during an intervention. This is even truer when dealing with volume sequences. The time spent in interpreting these images can be greatly decreased with segmentation algorithms, highlighting anatomical structures of interest, thus leading to a better image understanding and organ localization. Spatial images (2D and 3D) have been heavily studied. Spatio-temporal images (4D) are becoming widely available and they still present an unsolved computational challenge. Scanners output gigabytes of data and the trend is towards even higher definitions.
Explicit deformable models have been used as initial attempts for 4D segmentation. Free form deformations and simplex have been applied in the temporal domain to track 3D surfaces over time. However, 4D segmentation is not treated as a whole; the temporal dimension is rather treated separately. The surface of a particular frame serves as an initial guess for the next frame. Temporal correlation has been considered by adding 4D a priori knowledge in the segmentation. A probabilistic 4D atlas has been used and the segmentation is done with the EM algorithm. Temporal constraints have been added in a 4D deformable model.
As is also known, the level set method is a well-established segmentation algorithm in 2D and 3D images. Although this method is easily extendable to N-D, few works have been done in 4D. A 4D levelset has been used to approximate the aortic shape, the surface itself is computed with a graph-based method. Shape priors have been used to improve the segmentation of low quality images.
As is also known in the art, graph cuts have become the leading segmentation method guaranteeing a global optimal solution. It has already been used for 4D surface selection and reconstruction. In image segmentation, although being N-D interactive, Boykov and Jolly's method (Boykov, Y., Jolly, M. P.: Interactive organ segmentation using graph cuts. In: MICCAI, London, UK, Springer-Verlag (2000) 276-286) may be impractical for some 4D medical datasets using current processing capacities. New designs have been proposed to get around this issue. In Xu, N., Bansal, R., Ahuja, N.: Object segmentation using graph cuts based active contours. In: CVPR. Volume 2. (2003) II-46-53 vol. 2, active contours are simulated by evolving banded graph cuts. However, in this method, the band inner boundary has a smaller surface than the band outer boundary; the difference in surface area creates a shrinkage bias. Lazy snapping (Li, Y., Sun, J., Tang, C. K., Shum, H. Y.: Lazy snapping. ACM Trans. Graph. 23(3) (2004) 303-308, Li, Y., Sun, J., Shum, H. Y.: Video object cut and paste. In: IGGRAPH, New York, N.Y., USA, ACM Press (2005) 595-600) uses the graph cuts technique on watershed regions of the image. The algorithm pre-segmentation is however time consuming when using large datasets, and produces an unpredictable number of watershed regions. Moreover, the fine segmentation depends on the watershed boundaries, and as shown in Adams, R., Bischof, L.: Seeded region growing. IEEE Trans on PAMI 16(6) (1994)641-647, these boundaries are not necessarily robust to noise. Rather than watershed regions, the mean shift algorithm has been used in Wang, J., Bhat, P., Colburn, A. R., Agrawala, M., Cohen, M. F.: Interactive video cutout. In: SIGGRAPII, New York, N.Y., USA, ACM Press (2005) 585 594 to segment objects in a (2D+t) video. This method still relies on pre-segmented results, which are also time-consuming in this case. A different coarse-to-fine approach is the multilevel banded graph cuts method (Lombaert, H., Sun, Y., Grady, L., Xu, C.: A multilevel banded graph cuts method for fast image segmentation. In: ICCV, Washington, D.C., USA, IEEE Computer Society (2005) 259-265). The algorithm iteratively projects the results from a coarse image up to the fine resolution. Results in 2D and 3D are comparable to the standard graph cut algorithm. However, small and thin structures can easily be lost with this method when using very large 4D datasets. Active Graph Cuts (Juan, O., Boykov, Y.: Active graph cuts. In: CVPR. Volume 1. (2006) 1023-1029) could solve this problem as it retains the global optimality of the solution, but requires the same amount of memory than the standard graph cuts.
These graph cuts based techniques are all efficient with 2D and 3D images, but the memory required by large 4D datasets is prohibitive. The standard graph cuts method uses a graph where each of its node is associated with a unique voxel. The user initializes the algorithm (FIG. 1A) with seed points belonging to the object and to the background. Representing a 4D graph with all its nodes (V) and edges (E) requires a prohibitive amount of “memory. For example, with Boykov and Kolmogorov's maxflow implementation, 24|V|+14|E| bytes are required. That is over 21 GB for a 4D 10×2563 dataset. Additionally, the polynomial complexity makes graph cuts impractical using today's processing power.